﻿public class Solution
{
    private IList<IList<int>> result = new List<IList<int>>();
    private IList<int> res = new List<int>();
    
    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {
        Array.Sort(candidates); // 先排序
        bool[] used = new bool[candidates.Length];
        int start = 0;
        trackbacking(candidates, target, start, used);
        return result;
    }

    private void trackbacking(int[] candidates, int target, int start, bool[] used)
    {
        if (target == 0)
        {
            result.Add(new List<int>(res));
            return;
        }

        if (target < 0) return;

        for (int i = start; i < candidates.Length; i++)
        {
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            res.Add(candidates[i]);
            used[i] = true;
            target -= candidates[i];
            trackbacking(candidates, target, i+1, used);
            target += candidates[i];
            used[i] = false;
            res.RemoveAt(res.Count-1);
        }
    }

    public static void Main(string[] args)
    {
        int[] candidates = [10, 1, 2, 7, 6, 1, 5];
        int target = 8;

        Solution solution = new Solution();
        IList<IList<int>> result = solution.CombinationSum2(candidates, target);

        foreach (IList<int> res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }

    }
}